package window;
import java.util.*;
public class Ex238 {
    static class Solution {
        public int[] productExceptSelf1(int[] nums) {
            int len = nums.length;
            int[] left = new int[len], right = new int[len], res = new int[len];
            left[0] = 1;
            right[0] = 1;
            for(int i = 1; i < len; i++) {
                left[i] = left[i - 1] * nums[i - 1];
                right[i] = right[i - 1] * nums[len - i];
            }

            for (int i = 0; i < len; i++) {
                res[i] = left[i] * right[len - i - 1];
            }

            return res;
        }

        public int[] productExceptSelf(int[] nums) {
            int len = nums.length;
            int[] res = new int[len];
            res[0] = 1;
            
            //先算左边的乘积结果
            for (int i = 1; i < len; i++) {
                res[i] = res[i - 1] * nums[i - 1];
            }

            int last = nums[len - 1];
            //在算右边乘积结果，需要暂存上一次的乘积
            for (int i = len - 2; i >= 0; i--) {
                res[i] = res[i] * last;
                last *= nums[i];
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,2,3,4};
        int[] res = s.productExceptSelf(nums);
        System.out.println(Arrays.toString(res));
    }
}
